/*
 * @lc app=leetcode.cn id=234 lang=swift
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if head == nil { return true }

        var left: ListNode? = head
        var right: ListNode? = head
        while left != nil && right != nil {
            left = left?.next
            right = right?.next?.next
        }
        if right != nil {
            left = left?.next
        }

        // 反转链表
        func reverse(_ head: ListNode?) -> ListNode? {
            var pre: ListNode?, next: ListNode?
            var cur: ListNode? = head
            while cur != nil {
                next = cur?.next
                cur?.next = pre
                pre = cur
                cur = next
            }
            return pre
        }

        right = reverse(left)
        left = head
        while right != nil {
            if left!.val != right!.val {
                return false
            }
            left = left?.next
            right = right?.next
        }
        return true
    }
}
// @lc code=end

